package someTestExcemple.huaweiOd.unionFindSet;

//华为OD机试 - 服务器广播 - 并查集（Java 2024 E卷 200分）
//https://blog.csdn.net/guorui_java/article/details/142115442

import java.util.Arrays;
import java.util.Scanner;

/**
 * 并查集是一种非常有效的数据结构，用于处理不交集的合并及查询问题。在本题中，
 * 我们可以利用并查集来追踪服务器之间的连接关系，
 * 从而确定最少需要广播的服务器数量，即图中的连通分量数量。
 */

//其实是求该图有几个大的连通分量
public class Broadcast {

    private static int[] parent;
    private static int[] treeHeight;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        //服务器数量
        int N = arr.length;
        int[][] matrix = new int[N][N];
        matrix[0] = arr;
        for(int i=1;i<N;i++) {
            int[] arrI = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            matrix[i] = arrI;
        }
        sc.close();
        int count=0;
        //System.out.println(Arrays.deepToString(matrix));
        //1方法1-DFS
/*        boolean[] visited = new boolean[N];
        for(int i=0;i<N;i++) {
            if(visited[i] !=true) {
                dfs(matrix,i,visited,N);
                count++;
            }
        }
        System.out.println(count);*/

        //2用并查集，对这个图进行集合合并，服务器间可以连通的是一个集合，最后看这个图有几个不同的集合
        //并查集优化--路径压缩 -合并优化(比较树高合并，或者比较两数的节点数量大小进行合并)
        //其实还可以优化，最终可以省略高度数组或者节点大小数组，对parent数组进行优化
        //根节点用负数代表树高，非根节点，还是执行根节点
        //比如2,3节点是一个集合 parent[2] =-1表示树高为1，parent[3]=2表示节点3合并到节点2所在集合
        //但是代码可读性变差了
        parent = new int[N];
        treeHeight = new int[N];
        //集合初始化
        for(int i=0;i<N;i++) {
            parent[i] = i; //都指向自己
            treeHeight[i]=-1; //每棵树初始高度为-1
        }
        //对集合进行合并
        for(int i=0;i<N;i++) {
            for(int j=i+1;j<N;j++) {
                if(matrix[i][j] == 1) {
                    //两服务器相连通 合并集合
                    union(i,j);
                }
            }
        }

        //看合并后有几个集合，即找parent数组有几个根节点
        for(int i=0;i<N;i++) {
            if(parent[i] ==i) {
                count++;
            }
        }
        System.out.println(count);
    }
    public static void dfs(int[][] matrix,int node,boolean[] visited,int N) {
        visited[node] = true;
        for(int j=0;j<N;j++) {
            //有连接且未访问过
            if(matrix[node][j] ==1 && !visited[j]) {
             dfs(matrix,j,visited,N);
            }
        }
    }

    //并查集-查找操作

    public static int find(int x) {
        //还没找到根节点，继续向树往上查找
        if(parent[x] != x) {
            parent[x] = find(parent[x]); //路径压缩，最终使得每个非根节点，直接指向根节点
        }
        return parent[x];
    }

    //合并不同集合
    public static void union(int x,int y) {
        int rootX = find(x);
        int rootY = find(y);
        if(rootX != rootY) {
            //矮树合并到高树
            if(treeHeight[x] < treeHeight[y]) {
                parent[x] = rootY;
            } else if(treeHeight[x] > treeHeight[y]) {
                parent[y] = rootX;
            } else {
                //两树相等 合并后高度+1;
                parent[y] = rootX;
                treeHeight[x] ++;
            }
        }
    }
}
